                          Baraj, ziua 1
                   Problema 1 (Dreptunghiuri)

     Se consider[ n plan un dreptunghi de coordonate ntregi (mai mici dect 30.000). Suprafaa
acestui dreptunghi se mparte n dreptunghiuri mai mici, ale c[ror coordonate sunt tot ntregi. Vrfurile
acestor dreptunghiuri determin[ pe laturile celorlalte dreptunghiuri segmente. 
    Cunoscnd coordonatele a dou[ vrfuri opuse (stnga-jos, dreapta-sus) ale dreptunghiurilor mici,
se cere:
a) S[ se precizeze prin "da" sau "nu" dac[ este posibil s[ se traseze o linie continu[ care s[ taie toate
segmentele mici formate pe laturile dreptunghiurilor, fiecare segment fiind t[iat o singur[ dat[.
R[spunsul va fi nsoit de un mesaj justificativ care corespunde algoritmului folosit pentru a da r[spunsul.
In algoritm nu se va ncerca trasarea liniei pentru a putea preciza r[spunsul.
b)  In cazul n care s-a r[spuns "da", se va furniza un posibil traseu al liniei continue, specificnd
segmentele prin coordonatele extremit[ilor lor, n ordinea n care vor fi t[iate de linia continu[.
    In program se va citi un fiier text de intrare numit in.txt care cuprinde mai multe seturi de
date, separate prin cte o linie vid[. Liniile fiec[rui set de date vor conine, separate prin cte un spaiu,
coordonatele celor dou[ vrfuri opuse ale cte unui dreptunghi.
    R[spunsurile se vor afia pe ecran. Seturile de r[spunsuri vor fi separate prin linii vide.
Exemplu:
Fiierul in.txt conine liniile:
20 10 30 20
10 10 20 20
10 20 30 40
Se va afia:
da
.................................{  explicaii  }
(10,40)--(30,40); (30,40)--(30,20);  (30,20)--(30,10);  (30,10)--(20,10);
(20,10)--(10,10); (10,10)--(10,20);  (10,20)--(10,40);  (20,20)--(30,20);
(20,20)--(20,10); (10,20)--(20,20)

Not[: Timp maxim de executare pentru fiecare test: 30 secunde.
=============================================

       Baraj ziua 1
       Problema 2 (Joc cu obiecte)

     Fie un ir de k c[sue pe care se afl[ amplasate 2*n, (k2*n) piese de dou[ culori (jum[tate
roii i jum[tate albastre), astfel nct s[ fie ndeplinite condiile: 
   1) In fiecare c[su[ exist[ cel mult o pies[.
   2) Parcurgnd irul c[suelor de la stnga spre dreapta (sau invers), culorile pieselor vor alterna.
   3) Cea mai din stnga pies[ are culoarea roie.
                Dou[ persoane A i B particip[ la urm[torul joc: Alternativ, cei doi pot muta una din piesele lor
(A poate muta doar piese roii, iar B poate muta doar piese albastre) spre stnga sau spre dreapta, f[r[
a putea s[ri peste alte piese. Cel care nu mai poate muta, pierde. Iniial mut[ A. 
Se cere:
   a) S[ se determine dac[ juc[torul A are strategie sigur[ de ctig;
   b) In caz afirmativ s[ se determine prima mutare pe care o va efectua juc[torul A. Se va afia a cta
pies[ roie a fost mutat[, cu cte poziii, i n ce sens.
Restricii:
Numele fiierului de intrare se citete de la tastatur[.
Fiierul de intrare are urm[toarea structur[:
 - pe prima linie: num[rul pieselor de o culoare (n);
 - pe a doua linie: un ir de caractere, avnd elementele n mulimea {0,a,r} unde:
r = c[su[ ocupat[ de piesa roie;
a = c[su[ ocupat[ de piesa albastr[;
0 = c[su[ neocupat[. 
Num[rul c[suelor este mai mic sau egal cu 1000.
Ieirea se face pe ecran.
Exemplu:
Pentru fiierul de intrare:
1
0000r0000000a0
programul va trebui s[ afieze:
Juc[torul A are strategie sigur[ de catig.
A mut[ cu 7 poziii spre dreapta piesa 1.

Not[: Timp maxim de executare pentru fiecare test: 1 secund[.
==============================
     Baraj ziua 1
     Problema 3 (La firma Microsoft)

     La firma Microsoft exist[ foarte des informaii pe care Bill Gates ar dori s[ le fac[ cunoscute
n timpul cel mai scurt tuturor angajailor prezeni la sediul firmei, f[r[ s[-i convoace n sala de edine. 
    Nu poate folosi reeaua sau e-mailul, deoarece nu toi angajaii lucreaz[ pe calculatoare. Se va
folosi telefonul, deoarece la fiecare loc de munc[ exist[ telefon i, de regul[, oricare dou[ posturi pot
comunica ntre ele.
    - fiecare telefon se identific[ printr-un num[r;
    - ntr-un birou exist[ un singur telefon i, de regul[, cel puin o persoan[;
    - la telefon r[spunde o persoan[ desemnat[, numit[ n continuare persoan[ de contact; persoana
de contact preia informaia, o transmite imediat celor din birou (aceast[ transmitere nu necesit[ timp).
In prima unitate de timp transmite telefonic informaia la un anumit post, n a dou[ unitate de timp la
un alt post, .a.m.d. pn[ cnd s-au epuizat posturile pe care trebuie s[ le 
anune postul respectiv;
    - n aceeai unitate de timp vor putea transmite informaia respectiv[ mai multe posturi distincte
simultan;
    - fiec[rui telefon i se mai ataeaz[ un num[r intreg, care reprezint[ rangul persoanei de contact;
Bill Gates are rangul cel mai mare, iar un angajat care nu are subalterni are rangul 0;  un angajat cu rangul
i are n subordine pe toi angajaii avnd rang mai mic dect i.
    Scriei un program care s[ furnizeze zilnic, n fiecare diminea[, schema din care s[ rezulte cine
pe cine trebuie s[ anune, n cazul n care sosete o informaie care trebuie transmis[. Bill Gates a impus
urm[toarele reguli de transmitere a informaiilor:
    1) informaia trebuie s[ fie transmis[ ntotdeauna de c[tre o persoan[ avnd un anumit rang,
c[tre o persoan[ avnd rangul cel mult egal cu al celei care transmite;
    2) Bill Gates nu va ncepe transmiterea unei informaii noi, pn[ cnd cea n curs de transmitere
nu a ajuns la toi angajaii.
    Programul va fi rulat n fiecare diminea[ de eful personalului, care actualizeaz[, n prealabil,
fiierul cu care lucreaz[ programul. El marcheaz[ posturile de telefon care sunt n birouri din care toi
angajaii lipsesc (sunt bolnavi, au plecat n delegaie etc).
    Programul trebuie sa furnizeze o singur[ schem[, conform c[reia transmiterea informaiei are
loc n num[r minim de unit[i de timp.
Date de intrare:
    In fiierul de tip text, al c[rui nume se citete de la tastatur[,
- pe prima linie se afl[ un num[r ntreg n (1n100), reprezentnd num[rul posturilor telefonice
existente;
- pe urm[toarele n linii sunt informaii referitoare la cele n posturi telefonice:
- pe fiecare linie este scris num[rul unui post telefonic, urmat de un num[r ntreg care precizeaz[ rangul
persoanei de contact din biroul n care este telefonul respectiv; 
- cele dou[ numere ntregi sunt separate de un blanc;
- informaiile referitoare la posturi telefonice se succed n ordine cresc[toare dup[ num[rul telefonului;
- posturile de telefon, care sunt n birouri de unde toti angajaii lipsesc, sunt marcate printr-un caracter '*'
n faa celor dou[ informaii numerice, f[r[ spaiu. 
Date de ieire:
    In fiierul de ieire, de tip text, al c[rui nume se va citi de la tastatur[ se va scrie schema, sub
forma unor linii avnd urm[toarea structur[:
nr_de_telefoni (rangi)->nr_de_telefonj (rangj,timpk),..
unde:
 - nr_de_telefoni i rangi identific[ postul de la care se transmite;
 - nr_de_telefonj i rangj identific[ postul la care se transmite;
 - timpk este un num[r intreg i reprezint[ n a cta unitate de timp are loc transmisia;

    De asemenea, scrie n fiier eventualele linii telefonice care n ziua respectiv[ nu pot fi folosite
din cauza unor defeciuni.
- dup[ cele n linii referitoare la cele n posturi telefonice, urmeaz[ un num[r oarecare de linii n care sunt
precizate liniile defecte sub forma de perechi de numere de telefon, (separate de un blanc) ntre care nu
mai exist[ legatur[ direct[. 
    2) In cazul n care exist[ posturi telefonice care nu pot fi anunate din cauza c[ toate liniile
utilizabile sunt defecte, se va scrie n fiierul de ieire:
Posturile care nu pot fi anuntate telefonic:
nr1
nr2
...
nrk
unde:
- nri, (i=1,k) este num[rul postului de telefon (din cele k posturi depistate, care nu poate fi anunat.
Observaie:
    Corespunz[tor unui post telefonic, se vor preciza, separate de o virgul[ toate posturile anunate
de la telefonul respectiv.
Exemplu:
    Fiierul de intrare:
13
1 5
2 3
3 3
4 3
5 4
6 2
7 1
8 4
*9 3
*10 2
11 0
12 0
*13 0
    Fiierul de ieire poate s[ conin[:
1 (5)->5 (4,1), 8 (4,2), 3 (3,3), 11 (0,4)
5 (4)->2 (3,2), 4 (3,3), 12 (0,4)
8 (4)->6 (2,3)
2 (3)->7 (1,3)
Not[: Timp maxim de executare pentru fiecare test: 30 secunde.
====================================================

      Baraj, ziua 2
      Problema 4 (Problema aprovizion[rii)

     O reea de N (N10) magazine folosete un camion pentru a se aproviziona cu un anumit produs
de la cele 3 depozite en-gros cu care are contract. oferul camionului este pl[tit n funcie de distana
total[ parcurs[ de la depozite la magazine, lundu-se n considerare doar drumurile cnd este nc[rcat
(de la depozit la magazin). Camionul are capacitatea astfel nct poate transporta 
orice cantitate intervine n problem[, pentru a satisface toate cererile de la fiecare magazin. Fiind prieten
cu patronul, acesta v-a promis un premiu substanial dac[ reuii s[ g[sii o modalitate prin care oferul
s[ fie pl[tit ct mai puin, adic[ prin care s[ se g[seasc[ ruta care minimizeaz[ drumurile pe care 
le are de f[cut oferul.
    Se cunosc stocurile x(i), i=1,3 din produsul respectiv, existente la fiecare dintre depozite i
cererile r(j), j=1,N de la fiecare magazin.
Se mai impun urm[toarele condiii:
    - cantitatea total[ transportat[ de la orice depozit la magazin trebuie s[ fie egal[ cu cererea de
la acel magazin;
    - nu se admit transbord[ri: nu se poate transporta marfa de la un depozit la alt depozit, sau de la
un magazin la altul (nu se admit situaiile n care o parte din marf[ e l[sat[ la un magazin i restul dus[
la alt magazin sau la alt depozit).
Date de intrare:
Fiierul text, al c[rui nume se va citi de la tastatur[, va conine:
    - pe prima linie num[rul de magazine N;
    - urm[toarele linii vor conine distanele de la depozite la magazine (n ordinea cresc[toare a
depozitelor): pe o linie, distanele de la un depozit la magazinele 1,2,...,N separate de un spaiu;
    - urm[toarele trei linii vor conine stocurile x(i) de la depozite;
    - urm[toarele N linii vor conine cererile r(j) de la magazine.
Date de ieire:
Fiierul text de ieire out.txt va conine:
    - pe prima linie distana total[ minim[;
    - urm[toarele linii: pe cte o linie triplete de forma (i,j,k) cu semnificaia: se va parcurge
drumul de la depozitul i la magazinul j transportnd cantitatea k.
    Aceast[ list[ de triplete va fi ordonat[ cresc[tor dup[ num[rul depozitului i pentru acelai
depozit, cresc[tor dup[ num[rul magazinului.
    In cazul n care nu se poate realiza un astfel de parcurs n conformitate cu cerinele enunului se
va afia un mesaj corespunz[tor.
Observaie: 
Toate m[rimile care intervin n problem[ au valori ntregi, strict pozitive.
Exemplu:
Fie coninutul fiierului de intrare:
4
2 2 3 3
1 2 1 3
4 5 1 6
10
10
3
8
7
5
2
Fiierul de ieire va conine:
8
1 2 7
1 4 2
2 1 8
2 3 2
3 3 3
Not[: Timp maxim de executare pentru fiecare test: 30 secunde.
=================================================

      Baraj, ziua 2
      Problema 5 (Dominouri)

     Se consider[ o reea format[ din p[trate avnd latura 1, reea care are dimensiunile m linii
verticale i n linii orizontale, unde 5m,5n,m1000,n1000 i m+n este num[r impar.
S[ se g[seasc[ o acoperire a reelei, folosind piese de domino de dimensiuni 1*2, astfel nct orice linie
a reelei s[ intersecteze cel puin o pies[.
Date de intrare:
      - m i n, se vor citi de la tastatur[.
Date de ieire:
         In fiierul de tip text, al c[rui nume se va citi de la tastatur[, se va preciza amplasarea
dominourilor pe reea, folosind dou[ matrici: prima dintre ele se refer[ la segmentele orizontale i are
dimensiunea (n-1)*m, a doua matrice se refer[ la segmentele verticale i are dimensiunea n*n prezena
unui segment se va semnala prin caracterul 1, absena prin caracterul 0.
-     n fiierul de ieire, datele se vor scrie n felul urm[tor:
- n-1 linii care vor conine m caractere 0 sau 1, separate printr-un spaiu; nu se va pune spaiu n faa
primului caracter i dup[ ultimul caracter 0 sau 1 de pe linie;
- o linie de separaie, format[ din m caractere - (minus);
- n linii a cte m-1 caractere 0 sau 1, separate printr-un spaiu; nu se va pune spaiu n faa primului
caracter i dup[ ultimul caracter 0 sau 1 de pe linie.
Observaie:
    Segmentele orizontale se vor scrie n prima matrice de la stnga la dreapta i de sus n jos iar
segmentele verticale se vor scrie n a doua matrice de la stnga la dreapta i de sus n jos.
Exemplu:
Pentru m=5 i n=6.
Fiierul de ieire poate avea urm[torul coninut:
0 1 1 1 1
1 0 1 1 0
0 1 1 1 1
1 1 1 0 0
1 1 0 1 1
-----
1 0 1 0
____
1 1 0 1
1 1 0 1
1 0 1 1
0 1 1 1
0 1 1 0
Not[: Timp maxim de executare pentru fiecare test: 30 secunde.
============================

     Baraj, ziua 2
     Problema 6 (Expresii)

     Fie un num[r prim p. Pe mulimea {0,1,...,p-1} se definesc operaiile binare +,-,*,/
modulo p n modul urm[tor:
1) a+b modulo p este restul mp[ririi lui a+b la p; analog pentru *; 
2) Expresia a-b este definit[ ca fiind soluia ecuaiei b+x=a (modulo p); analog 
pentru /;
    Se tie c[ ecuaia b+x=a are ntotdeauna soluie unic[, iar b*x=a are soluie unic[ pentru orice
bc0; pentru b=0 operaia a/b nu e definit[.
    De exemplu, dac[ p=11 atunci 6+7=2, 6-7=10, 6*7=9, 6/7=4. 
Se tie c[ adunarea i nmultrea modulo p sunt comutative, asociative, posed[ elemente neutre (pe 0,
respectiv 1), adunarea este distributiv[ fa[ de nmulire. 
    In plus, pentru orice a exist[ b astfel nct a+b=0; notnd b cu (-a) avem c-a=c+(-a)=c+b,
pentru orice c.
    De asemenea, pentru orice ac0 exist[ b astfel nct a*b=1; notnd b cu (1/a) avem c[
c/a=c*(1/a)=c*b.
    Dndu-se un num[r prim p, un ntreg d ntre 0 i p-1 i un ir de numere cuprinse fiecare ntre
0 i p-1, se cere s[ se introduc[ ntre elementele irului operatorii +,-,*,/ i parantezele
corespunz[toare, astfel nct s[ se obin[ o expresie corect[ a c[rei valoare s[ fie d (lucr[nd n
aritmetica modulo p).
In caz c[ acest lucru nu este posibil, se va afia un mesaj corespunz[tor.
Intrarea:
    Numele fiierului de intrare se citete de la tastatura. Acest fiier conine dou[ linii: 
- pe prima linie se g[sesc trei numere ntregi: p,n i d, separate prin spaii (2p23, p prim,
1n30, 0dp-1).
- pe urm[toarea linie se g[sete irul de numere ce formeaz[ expresia (n numere ntregi cuprinse ntre
0 i p-1).
Ieirea:
    Numele fiierului de ieire se citete de la tastatur[. Acest fiier va conine o singur[ linie pe care
se va g[si expresia generat[ sau mesajul:
Nu exista solutie.
Expresia va fi parantezat[ complet (fiecare operator va avea o pereche de paranteze ataate).
Exemple:
1) Intrare:
11 3 6
4 7 9
O ieire corect[:
(4+(7/9))
2) Intrare:
11 3 7
1 1 1
Ieire:
Nu exista solutie.
Not[: Timp maxim de executare pentru fiecare test: 1 minut.
=====================================

     Baraj ziua 3
     Problema 7 (KWIC-index)

     Dndu-se o list[ de fraze i o list[ de cuvinte de ignorat, s[ se scrie un program care genereaz[,
pornind de la o list[ de fraze, o list[ "indexat[" a acestora, numit[
               KWIC-index (Key Word In Context)
    Orice cuvnt care nu apare n lista de cuvinte de ignorat este un cuvnt cheie, deci un cuvnt dup[
care KWIC-indexul este ordonat.
    Astfel, dac[ lista de fraze este:
Concurs de baraj pentru lotul restrans.
Suntem la Cluj in luna mai.
Toti concurentii sunt bine pregatiti.
Concursul este greu.
    iar lista de cuvinte de ignorat este:
de,pentru,la,in,este,toti,sunt,suntem
KWIC-indexul generat va fi
                   Concurs de BARAJ pentru lotul restrans.
        Toti concurentii sunt BINE pregatiti.
                    Suntem la CLUJ in luna mai.
                         Toti CONCURENTII sunt bine pregatiti.
                              CONCURS de baraj pentru lotul restrans.
                              CONCURSUL este greu.
               Concursul este GREU.
      Concurs de baraj pentru LOTUL restrans.
            Suntem la Cluj in LUNA mai.
       Suntem la Cluj in luna MAI.
   Toti concurentii sunt bine PREGATITI.
Concurs de baraj pentru lotul RESTRANS.
    S[ se scrie un program care, pe baza unei liste de fraze, creaz[ KWIC-indexul corespunz[tor:
Date de intrare:
    In fiierul de tip text, al c[rui nume se citete de la tastatur[, se va da lista de fraze.
Frazele conin cuvinte separate printr-un blanc. Nu exist[ semne de punctuaie, toate caracterele sunt litere
mici i fraza se termin[ cu caracterul '.'.
Un cuvnt are mai puin de 20 caractere; exist[ cel mult 20.000 cuvinte.
    Intr-un alt fiier de tip text, al c[rui nume se citete de la tastatur[, se va da lista cuvintelor
ignorate. Aceste cuvinte sunt scrise unul pe o linie.
Date de ieire:
    In fisierul de ieire, al c[rui nume se citete de la tastatur[, se va scrie KWIC-indexul generat.
Fiecare fraz[ se scrie pe o linie nou[.
Exemplu:
    Pentru coninutul fiierului de intrare cu lista frazelor:
concurs de baraj pentru lotul restrans.
suntem la cluj in luna mai.
toti concurentii sunt bine pregatiti.
concursul este greu.
    i coninutul fiierului de intrare al cuvintelor ignorate:
de
pentru
la
in
este
toti
sunt
suntem
    conintulul fiierului de iesire va fi:
concurs de baraj pentru lotul restrans.
toti concurentii sunt bine pregatiti.
suntem la cluj in luna mai.
toti concurentii sunt bine pregatiti.
concurs de baraj pentru lotul restrans.
concursul este greu.
concursul este greu.
concurs de baraj pentru lotul restrans.
suntem la cluj in luna mai.
suntem la cluj in luna mai.
toti concurentii sunt bine pregatiti.
concurs de baraj pentru lotul restrans.

Not[: Timp maxim de execuie: 30 secunde.
================================================

      Baraj ziua 3
      Problema 2 (Statui)

     Primarul unui ora dorete s[ amplaseze ct mai multe statui, cel mult una ntr-o pia[. Oraul
este vizitat de diverse oficialit[i care sosesc la aeroport i trebuie transportate la prim[rie pe un drum
de lungime minim[. Primarul dorete s[ poat[ transporta oaspeii astfel nct, fie s[ vad[ toate statuile,
fie s[ nu vad[ nici o statuie.
    Cunoscnd reeaua stradal[ i poziiile aeroportului i prim[riei n aceast[ reea, s[ se determine
unde trebuie plasate statuile i care sunt cele dou[ trasee, astfel nct num[rul statuilor s[ fie maxim.
Intrarea:
    Datele de intrare se citesc dintr-un fiier al c[rui nume se d[ de la tastatur[. Fiierul conine:
- pe prima linie num[rul n de piee din ora; prim[ria se afl[ n piaa num[rul 1, aeroportul n piaa
cu num[rul n(n150);
- pe urm[toarele n linii se g[sesc cte n numere ntregi nenegative; al j-lea num[r de pe a i-a linie
reprezeint[ lungimea str[zii de la piaa avnd num[rul i la piaa cu num[rul j sau 0 dac[ i=j sau nu
exist[ strad[. datorit[ sensurilor unice, se poate ca distana de la i la j s[ nu fie egal[ cu distana de
la j la i.
    Datele din fiierul de intrare asigur[ existena cel puin a unui drum ntre aeroport i prim[rie.
ieirea:
    Ieirea se face ntr-un fiier text al c[rui nume se citete de la tastatur[. acest fiier va conine:
- pe prima linie num[rul s de statui urmat de lista pieelor n care urmeaz[ a fi amplasate;
- pe a doua linie num[rul de piee de pe drumul f[r[ statui, urmat de lista pieelor, n ordine, de la
aeroport la prim[rie (inclusiv capetele);
- pe a treia linie num[rul de piee de pe drumul ce viziteaz[ toate statuile, urmat de lista pieelor, n
ordine, de la aeroport la prim[rie (inclusiv capetele).
    Se cere o singur[ soluie.
Precizare: Att la intrare ct i la ieire datele de pe o linie sunt separate printr-un spaiu.
Exemplu:
Intrare:
5
0 2 0 3 0
2 0 2 2 0
0 2 0 1 2
3 1 0 0 3
0 0 2 3 0
    o ieire corect[:
2 2 3
3 5 4 1
4 5 3 2 1
Not[: Timp de executare maxim: 30 secunde.
==============================================

     Baraj ziua 3
     Poblema 3 (Tetris)

     Se dau n obiecte de apte forme diferite, formate din cte patru p[tr[ele, conform figurii de mai
jos:

  ----------------          ---------       ---------           -----
  |    |    |    |          |   |   |       |   |   |           |   |
  ----------------      -------------       -------------       -----
       |    |           |   |   |               |   |   |       |   |
       ------           ---------               ---------       -----
            (1)                  (2)                 (3)        |   |
                                                                -----
       ---------         -------------               -----      |   |
       |   |   |         |   |   |   |               |   |      -----
       ---------         -------------       -------------       (7)
       |   |   |                 |   |       |   |   |   |
       ---------                 -----       -------------
          (4)                     (5)                (6)

    Se d[ o tabl[ dreptunghiular[ avnd n/3 linii de cte 12 p[tr[ele care trebuie acoperite cu
asemenea obiecte (n este divizibil cu 3). Planul tablei este identic cu planurile celor n obiecte.
Dndu-se cele n obiecte, ele trebuie puse pe tabl[ prin translat[ri i rotaii cu 90o,180o i 270o n
propriul lor plan, astfel nct s[ nu r[mn[ nici una din p[tr[ele neacoperit[, respectiv obiectele s[
nu se suprapun[. Cu cele n obiecte date ntotdeauna se poate acoperi tabla, respectnd cerinele problemei.
Date de intrare:
    Fiierul de tip text, al c[rui nume se citete de la tastatur[, are urm[toarea structur[:
- pe prima linie un num[r ntreg, reprezentnd num[rul de obiecte (n18);
- pe urm[toarea linie se afl[ numerele de identificare ale obiectelor; obiectele sunt ntr-o succesiune
oarecare.
Date de ieire:
    In fiierul de ieire se va scrie o matrice avnd n/3 linii i 12 coloane care va fi construit[ n
felul urm[tor:
    Corespunz[tor fiec[rui obiect se va scrie, respectnd forma obiectului, de patru ori num[rul de
ordine al s[u, adic[ indicele obiectului n irul din fiierul de intrare. Elementele matricei se vor scrie n
fiier linie dup[ linie, desp[rite printr-un blanc. Nu se vor pune blancuri n faa primei coloane i dup[
ultima coloan[. Se cere o singur[ soluie.
Exemplu: Pentru coninutul fiierului de intrare:
6
7 7 4 4 6 6
coninutul fiierului de ieire va putea fi:
2 2 2 2 3 3 4 4 5 5 5 6
1 1 1 1 3 3 4 4 5 6 6 6
Not[: timp maxim de executare: 1 minut.
======================================================

                          Baraj ziua 4
Problema nr. 10 (Demonstrare automat[ folosind metoda rezoluiei)

     Pe baza unor echivalene logice tebuie s[ se demonstreze valabilitatea unei concluzii. clauzele
echivalente enunurilor i concluziei negate se vor citi dintr-un fiier text al c[rui nume se citete de la
tastatur[.
    Dac[ exist[ mai multe demonstraii, se va preznta una dintre ele. Intotdeauna exist[ o
demontraie.
Date de intrare:
    Pe fiecare linie a fiierului se g[sete cte o clauz[.
    Clauzele provenind din enunuri sunt separate printr-o linie vid[ de clauzele provenind din
concluzie.
    Clauzele satisfac umr[toarele condiii:
  - numele oric[rui predicat este o liter[ mare;
  - numele oric[rei funcii este o liter[ mic[;
  - numele oric[rei constante este o liter[ mare;
  - numele oric[rei variabile este o liter[ mic[;
  - delinitatorii argumentelor predicatelor i funciilor sunt paranteze rotunde;
  - separatorul termenilor din interiorul predicatelor i funciilor este virgula (',');
  - pentru negaie logic[ se folosete caracterul ~;
  - pentru operatorul "sau logic" se va folosi caracterul |;
  - argumentele funciilor sunt numai constante sau variabile;
Date de ieire:
    In fiierul deieire, al c[rui nume se va citi de la tastatur[, se vor scrie:
  - clauzele reprezentnd enunurile i concluzia negat[ (deci, cele citite din fiierul de intrare) numerotate;
  - clauzele deduse ulterior, numerotate, i numerele clauzelor folosite (n faa clauzei se fal[ num[rul
ei, urmat ntre paranteze de numerele clauzelor folosite).
Observaie:
    Clauza vid[ se va nota cu caracterul _ (underscore);
    In fiierul de ieire nu va exista caracterul blanc.
Exemplu: (tranzitivitatea relaiei de egalitate):
    Fie coninutul fiierului de intrare:
P(A,B)
P(B,C)
~P(x,y)|~P(y,z)|P(x,z)

~P(A,C)
    Coninutul fiierului de ieire va putea fi:
1 P(A,B)
2 P(B,C)
3 ~P(x,y)|~P(y,z)|P(x,z)
4 ~P(A,C)
5 (3,4)~P(A,y)|~P(y,C)
6 (1,5)~P(B,C)
7 (2,6)_
     Timp maxim de execuie: 30 secunde.
================================================

     Baraj ziua 4
     Problema 11 (Bilete de autobuz)

     Se consider[ un bilet de autobuz n care zona perforat[ are n*n p[tr[ele i pe care se vor face
k perforaii. Dac[ biletul este introdus n aparatul de compostat cu partea imprimat[, vom spune c[ s-a
folosit faa. In caz contrar vom spune c[ s-a folosit dosul. Biletul nu se poate introduce n aparat dect
cu faa sau cu dosul, deoarece pe una din p[ri este prins de cotor. Dac[ un bilet a fost compostat pe dos,
perforaiile obinute formeaz[ configuraia "oglind[" a unei configuraii obinute prin compostare pe fa[.
    Pentru n i k date, s[ se genereze toate configuraiile astfel nct o configuraie care se genereaz[
s[ nu fie oglinda nici unei configuraii deja generate. (Prin aceasta se urm[rete ca la un eventual control
s[ se poat[ stabili f[r[ ambiguitate dac[ biletul respectiv a fost sau nu compostat ntr-o anumit[ zi n
care a fost valabil[ o anumit[ configuraie sau oglinda sa, indiferent dac[ s-a folosit la compostare faa
sau dosul biletului).
Date de intrare:
    Valorile lui n(2n9) i k(1k4) se vor introduce de la tastatur[.
Date de ieire:
    Intr-un fiier text al c[rui nume se va citi de la tastatur[, se va scrie pe fiecare linie o configuraie
sub forma:
i1j1i2j2..ikjk
unde: ipjp(p=1,k) sunt coordonatele perforaiilor, ip reprezint[ linia, jp reprezint[ coloana.
    Configuraiile trebuie scrise n fiierul de ieire n ordine lexicografic[.
Exemplu:
Pentur n=3 i k=2 coninutul fiierului de ieire va fi:
1112
1113
1121
1122
1123
1131
1132
1133
1221
1222
1231
1232
2122
2123
2131
2132
2133
2231
2232
3132
3133
Not[: Timp maxim de executare: 1 minut;
=================================================

     Baraj ziua 4
     Problema 12 (Planific[ri cu costuri)

     Se d[ o main[ pe care se execut[ n(n100) lucr[ri. Fiecare lucrare sosete la un moment
t(i), cunoscut de la nceput. Toate lucr[rile au aceeai durat[ de execuie, notat[ cu cd. Fiecare lucrare
va fi planificat[ spre a fi nceput[ la un moment t1(i)t(i), astfel nct s[ fie respectate urm[toarele
reguli:
1) orice lucrare se execut[ integral, f[r[ a fi ntrerupt[;
2) nu pot fi n execuie dou[ lucr[ri simultan;
3) ntrzierea nceperii unei lucr[ri cost[ ct*(t1(i)-t(i)) unde ct este acelai pentru toate
lucr[rile;
4) fiecare unitate de timp n care maina este n funciune, dar nu este folosit[ (nu este planificat[ nici
o lucrare) cost[ cf;
5) fiecare pornire a mainii cost[ cp;
6) iniial maina este oprit[.
    Se cere s[ se planifice toate lucr[rile, precum i pornirile i opririle mainii, astfel nct s[ se
minimizeze costul total. In cazul n care exist[ mai multe soluii optime se va scrie n fiierul de ieire
una din ele.
Intrarea: 
    Datele de intrare se citesc dintr-un fiier text al c[rui nume se citete de la tastatur[:
- pe prima linie cinci numere ntregi strict pozitive: n,ct,cf,cp,d separate prin blanc;
- pe urm[toarele n linii se dau momentele sosirii lucr[rilor, n ordine cronologic[, cte unul pe linie:
t(i) sunt numere pozitive.
Ieirea:
    Ieirea se face ntr-un fiier text al c[rui nume se citete de la tastatur[. Acest fiier conine:
- pe primele cn linii vor fi scrise momentele t1(i) la care sunt planificate lucr[rile; acestea vor fi date
n ordinea n care apar lucr[rile la fiierul de intrare;
- pe urm[toarea linie va apare num[rul k de porniri ale mainii;
- pe urm[toarele k linii vor fi date momentele pornirii i opririi mainii, n ordine cronologic[ (pe fiecare
linie va apare momentul pornirii urmat corespunz[tor pentru oprire, cele dou[ numere fiind separate prin
blanc).
Exemplu:
Intrare:
3 2 3 10 5
1
11
21
    o ieire corect[:
6
11
21
2
6 16
21 26
    Costul minim n acest caz este: 2*(6-1)+10*2=30 (dat de o ntrziere de 6-1=5 unit[i de
timp pentru prima lucrare i de cele dou[ porniri ale mainii).
Not[: Timp maxim de executare: 30 secunde;
Punctaj maxim: 100 puncte.
==========================================
